struct Solution;


impl Solution {
    fn stone_game_self(piles: Vec<i32>) -> bool {
        let sum: i32 = piles.iter().sum();

        let len = piles.len();
        let mut vec = vec![vec![-1; len]; len];
        Solution::dp(&mut vec, 0, len - 1, &piles);
        vec[0][len - 1] * 2 > sum
    }

    // dp辅助算法
    fn dp(arr: &mut Vec<Vec<i32>>, start: usize, end: usize, piles: &[i32]) {
        if arr[start][end] != -1 {
            return;
        }

        if start + 1 == end {
            arr[start][end] = i32::max(piles[start], piles[end]);
            return;
        }

        Solution::dp(arr, start + 1, end - 1, piles);
        Solution::dp(arr, start + 2, end, piles);

        let start_choice = i32::min(arr[start + 1][end - 1], arr[start + 2][end]) + piles[start];

        Solution::dp(arr, start + 1, end - 1, piles);
        Solution::dp(arr, start, end - 2, piles);

        let end_choice = i32::min(arr[start + 1][end - 1], arr[start][end - 2]) + piles[end];

        arr[start][end] = i32::max(start_choice, end_choice);
    }

    fn stone_game(piles: Vec<i32>) -> bool {
        let len = piles.len();
        let mut vec = vec![vec![0; len]; len];

        for i in 0..len {
            vec[i][i] = piles[i];
        }

        for i in 1..len {
            for j in 0..(len - i) {
                vec[j][i + j] = i32::max(piles[j] - vec[j + 1][j + i], piles[i + j] - vec[j][i + j - 1]);
            }
        }

        vec[0][len - 1] > 0
    }
}

fn main() {
    Solution::stone_game_self(vec![]);
    Solution::stone_game(vec![]);
}
